#pragma once

#include <algorithm>
#include <functional>

#include "ezstl_iterator_base.hpp"

namespace ezstl {

namespace heap_detail {

/*
parent index = (i - 1) / 2
left child index = 2 * i + 1;
right child index = 2 * i + 2;
*/

// TODO: 尚未应用移动语义，待move函数实现后处理

/////////

template <typename RandomAccessIterator, typename Distance, typename T,
          typename Compare>
void __up(RandomAccessIterator first, Distance holeIndex, Distance topIndex,
          T value, Compare comp) {
  Distance parent = (holeIndex - 1) / 2;  // 计算父节点
  while (holeIndex > topIndex &&
         comp(*(first + parent), value)) {       // 不是堆顶并且父节点小于当前值
    *(first + holeIndex) = (*(first + parent));  // 父节点下移
    holeIndex = parent;                          // 更新当前位置为父节点位置
    parent = (holeIndex - 1) / 2;
  }
  *(first + holeIndex) = (value);  // 将值放入正确位置
}  // up

template <typename RandomAccessIterator, typename Distance, typename T,
          typename Compare>
void __down(RandomAccessIterator first, Distance holeIndex, Distance len,
            T value, Compare comp) {
  Distance topIndex = holeIndex;
  Distance secondChild = 2 * holeIndex + 2;  // 右子结点位置
  while (secondChild < len) {                // 右子结点存在
    if (comp(*(first + secondChild),
             *(first + (secondChild - 1))))  // 比较左右子结点 选择较大的一个
      secondChild--;
    *(first + holeIndex) = (*(first + secondChild));  // 子结点上移
    holeIndex = secondChild;  // 更新当前位置为子结点位置
    secondChild = 2 * (secondChild + 1);
  }
  if (secondChild == len) {
    *(first + holeIndex) = *(first + (secondChild - 1));
    holeIndex = secondChild - 1;
  }
  __up(first, holeIndex, topIndex, (value), (comp));
}  // down

template <typename RandomAccessIterator, typename Compare>
inline void __push_heap(RandomAccessIterator first, RandomAccessIterator last,
                        Compare &comp) {
  // 调用时新元素已经被放入容器最底端
  using Distance =
      typename iterator_traits<RandomAccessIterator>::difference_type;
  using T = typename iterator_traits<RandomAccessIterator>::value_type;
  T value = (*(last - 1));
  heap_detail::__up(first, Distance(last - first - 1), Distance(0), (value),
                    std::move(comp));
}

// 弹出堆顶元素
template <typename RandomAccessIterator, typename Compare>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                       Compare &comp) {
  using Distance =
      typename iterator_traits<RandomAccessIterator>::difference_type;
  using T = typename iterator_traits<RandomAccessIterator>::value_type;
  if (last - first > 1) {
    --last;
    T value = *last;   // 保存最后一个元素
    *last = (*first);  // 将第一个元素移动到最后一个位置
    heap_detail::__down(first, Distance(0), Distance(last - first), (value),
                        std::move(comp));
  }
}

template <typename RandomAccessIterator, typename Compare>
inline void __sort_heap(RandomAccessIterator first, RandomAccessIterator last,
                        Compare &comp) {
  while (last - first > 1) heap_detail::__pop_heap(first, last--, comp);
}

template <typename RandomAccessIterator, typename Compare>
inline void __make_heap(RandomAccessIterator first, RandomAccessIterator last,
                        Compare &comp) {
  using Distance =
      typename iterator_traits<RandomAccessIterator>::difference_type;
  using T = typename iterator_traits<RandomAccessIterator>::value_type;
  if (last - first < 2) return;
  Distance len = last - first;
  // 第一个非叶子节点
  Distance parent = (len - 2) / 2;
  while (true) {
    heap_detail::__down(first, parent, len, *(first + parent), (comp));
    if (parent == 0) return;
    --parent;
  }
}

}  // namespace heap_detail

// TODO: 但前使用标准库中的move, less函数，待move, less函数实现后处理

//////////

template <typename RandomAccessIterator, typename Compare>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,
                      Compare comp) {
  heap_detail::__push_heap(first, last, (comp));
}

template <typename RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
  std::less<typename iterator_traits<RandomAccessIterator>::value_type> less;
  heap_detail::__push_heap(first, last, (less));
}

template <typename RandomAccessIterator, typename Compare>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp) {
  heap_detail::__pop_heap(first, last, (comp));
}

template <typename RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
  std::less<typename iterator_traits<RandomAccessIterator>::value_type> less;
  heap_detail::__pop_heap(first, last, (less));
}

template <typename RandomAccessIterator, typename Compare>
inline void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
                      Compare comp) {
  heap_detail::__sort_heap(first, last, (comp));
}

template <typename RandomAccessIterator>
inline void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  std::less<typename iterator_traits<RandomAccessIterator>::value_type> less;
  heap_detail::__sort_heap(first, last, (less));
}

template <typename RandomAccessIterator, typename Compare>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last,
                      Compare comp) {
  heap_detail::__make_heap(first, last, (comp));
}

template <typename RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
  std::less<typename iterator_traits<RandomAccessIterator>::value_type> less;
  heap_detail::__make_heap(first, last, (less));
}

}  // namespace ezstl